package lc20240524;

import lc20240521.TreeNode;

import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Demo1 {
    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        TreeNode p = root.left.left; // Node 4
        TreeNode q = root.left.right; // Node 5

        System.out.println(findLCA1(root, p, q).val);

    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        Stack<TreeNode> StackToP = new Stack<>();
        Stack<TreeNode> StackToQ = new Stack<>();

        if (!findPath(root, p, StackToP) || !findPath(root, q, StackToQ)) {
            return null;
        }
        return findLCA(StackToP, StackToQ);
    }

    //找路径
    public static boolean findPath(TreeNode root, TreeNode target, Stack<TreeNode> path) {
        if (root == null) {
            return false;
        }
        path.push(root);
        if (root == target)
            return true;
        if (findPath(root.left, target, path)) {
            return true;
        }
        if (findPath(root.right, target, path)) {
            return true;
        }
        path.pop();
        return false;
    }

    public static TreeNode findLCA(Stack<TreeNode> pathToP, Stack<TreeNode> pathToQ) {
        Stack<TreeNode> Stack1 = new Stack<>();
        Stack<TreeNode> Stack2 = new Stack<>();

        while (!pathToP.isEmpty()) {
            Stack1.push(pathToP.pop());
        }
        while (!pathToQ.isEmpty()) {
            Stack2.push(pathToQ.pop());
        }

        TreeNode commonAncestor = null;
        while (!Stack1.isEmpty() && !Stack2.isEmpty()) {
            TreeNode a = Stack1.pop();
            TreeNode b = Stack2.pop();
            if (a == b) {
                commonAncestor = a;
            } else {
                break;
            }
        }
        return commonAncestor;
    }

    //递归方法
    public static TreeNode findLCA1(TreeNode root, TreeNode p, TreeNode q) {
        // Base case: if root is null or root is one of p or q
        if (root == null || root == p || root == q) {
            return root;
        }

        // Recursively find LCA in the left and right subtrees
        TreeNode left = findLCA1(root.left, p, q);
        TreeNode right = findLCA1(root.right, p, q);

        // If p and q are found in different subtrees, root is their LCA
        if (left != null && right != null) {
            return root;
        }

        // Otherwise, LCA is in either the left or right subtree
        return left != null ? left : right;
    }
}

